1. Technical Field of the Invention
The invention relates generally to communication systems; and, more particularly, it relates to decoding of signals employed in such communication systems.
2. Description of Related Art
Data communication systems have been under continual development for many years. One such type of communication system that has been of significant interest lately is a communication system that employs iterative error correction codes. Of particular interest is a communication system that employs LDPC (Low Density Parity Check) code. Communications systems with iterative codes are often able to achieve lower bit error rates (BER) than alternative codes for a given signal to noise ratio (SNR).
A continual and primary directive in this area of development has been to try continually to lower the SNR required to achieve a given BER within a communication system. The ideal goal has been to try to reach Shannon's limit in a communication channel. Shannon's limit may be viewed as being the data rate to be used in a communication channel, having a particular SNR (Signal to Noise Ratio), that achieves error free transmission through the communication channel. In other words, the Shannon limit is the theoretical bound for channel capacity for a given modulation and code rate.
LDPC codes are oftentimes referred to in a variety of ways. For example, iterative soft decoding of LDPC codes may be implemented in a number of ways including based on the BP (Belief Propagation) algorithm, the SP (Sum-Product) algorithm, and/or the MP (Message-Passing) algorithm; the MP algorithm is sometimes referred to as a Sum Product/Belief Propagation combined algorithm. While there has been a significant amount of interest and effort directed towards these types of LDPC codes, regardless of which particular manner of iterative decoding algorithm is being employed in the specific case (3 of which are enumerated above: BP, SP, and MP), there still is ample room for improvement in the implementation and processing to be performed within a communication device to complete such decoding. For example, there are a variety of relatively complex and numerically burdensome calculations, data management and processing that must be performed to effectuate the accurate decoding of an LDPC coded signal.
LDPC code has been shown to provide for excellent decoding performance that can approach the Shannon limit in some cases. For example, some LDPC decoders have been shown to come within 0.3 dB (decibels) from the theoretical Shannon limit. While this example was achieved using an irregular LDPC code of a length of one million, it nevertheless demonstrates the very promising application of LDPC codes within communication systems.
FIG. 4 is a diagram illustrating a prior art embodiment of MP (Message Passing) decoding functionality 400. In this prior art embodiment, the bit metrics 410 are initialized and provided to one or more bit engine processors (shown generally as bit engine 421, bit engine 422, bit engine 423, . . . , and bit engine 424). The one or more bit engine processors 421-424 perform bit node processing by updating a plurality of edge messages with respect to a plurality of bit nodes, Medgeb, using the initialized bit metrics 410.
This results in the generation of the updated edge messages with respect to a plurality of bit nodes, Medgeb, of the first generation. Thereafter, these updated edge messages with respect to a plurality of bit nodes, Medgeb, are provided to and stored in an edge memory 430 from which they may subsequently be appropriately retrieved for check node processing using one or more check engine processors (shown generally as check engine 441, check engine 442, check engine 443, . . . , and check engine 444). The one or more check engine processors 441-444 perform check node processing by updating a plurality of edge messages with respect to a plurality of check nodes, Medgec, using the most recently updated plurality of edge messages with respect to a plurality of bit nodes, Medgeb. Thereafter, these updated edge messages with respect to a plurality of check nodes, Medgec, are provided to and stored in the edge memory 430 from which they may subsequently be appropriately retrieved for bit node processing using the one or more bit engine processors 421-424.
The one or more bit engine processors 421-424 and the one or more check engine processors 441-444 operate cooperatively to perform iterative decoding processing that involves updating the plurality of edge messages with respect to a plurality of bit nodes, Medgeb, and updating the plurality of edge messages with respect to a plurality of check nodes, Medgec. After a final decoding iteration, the most recently updated plurality of edge messages with respect to a plurality of bit nodes, Medgeb, is employed to generate soft bit information from which subsequent hard decisions are made to make best estimates of the one or more information bits that have undergone LDPC encoding.
In addition, there are also two known prior art approaches by decoding of LDPC coded signals may be performed in accordance with a LMP (Layered Message Passing) decoding approach. The following two references describe the LMP decoding approach.
[a] M. M. Mansour and N. R. Shanbhag, “High-throughput LDPC decoder,” IEEE Trans. Inform. Theory, vol. 11, no. 6, pp. 976-996, December 2003.
[b] D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” Signal Processing Systems, 2004, SIPS 2004, IEEE Workshop on 13-15 October 2004, pp. 107-112.
Using the LMP decoding approach, the parity check matrix, H, of an LDPC code has the following form.H=[H1H2 . . . HL]T.  (EQ 1)
In this form, each of the sub-matrices, Hi, has the same number of rows. Moreover, each of the sub-matrices, Hi, may further be decomposed as follows:Hi=└Hi,1Hi,2 . . . Hi,M┘.  (EQ 2)
In this decomposed form, it is noted that each of these sub-matrices, Hi,j, is either a p×p matrix in which all elements are either 0 (i.e., an all zero-valued matrix) or a p×p matrix that is a permutation of the identity matrix. While each of the two prior art decoding approaches can provide a means to reduce the total number of decoding iterations required (e.g., because of their layered decoding approach), each of these two prior art decoding approaches is significantly limited, in that, they can only accommodate a sub-matrix, Hi,j, that is permutation of a single p×p identity matrix.
The use of LDPC coded signals continues to be explored within many newer application areas. One such application area is that of digital video broadcasting. The Digital Video Broadcasting Project (DVB) is an industry-led consortium of over 260 broadcasters, manufacturers, network operators, software developers, regulatory bodies and others in over 35 countries committed to designing global standards for the global delivery of digital television and data services. Publicly available information concerning the DVB is available at the following Internet address:
“http://www.dvb.org/”
The DVB-S2 (i.e., DVB-Satellite Version 2) draft standard is also publicly available via this Internet address, and the current DVB-S2 draft standard may be downloaded in Adobe PDF format at the following Internet address:
“http://www.dvb.org/documents//en302307.v1.1.1.draft.pdf”
The entire contents of this current DVB-S2 draft standard, “Draft ETSI EN 302 307 V1.1.1 (2004-06), Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications” is hereby incorporated herein by reference in its entirety and made part of the present disclosure for all purposes.
In addition, the standard “ETSI EN 302 307 V1.1.1 (2005-03), Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications” was formally ratified by the ETSI (European Telecommunications Standards Institute) in March 2005. The entire contents of this standard is hereby incorporated herein by reference in its entirety and made part of the present disclosure for all purposes.
In addition, DVB-S2 uses a powerful FEC (Forward Error Correction) system based on concatenation of BCH (Bose-Chaudhuri-Hocquenghem) outer coding with LDPC inner coding. The result is performance which is at times only 0.7 dB from the Shannon limit. The choice of FEC parameters depends on the system requirements. With VCM (Variable Coding and Modulation) and ACM (Adaptive Coding and Modulation), the code rates can be changed dynamically, on a frame by frame basis.
The multiple operational parameters to which a receiving device, that includes a decoder, must operate to be DVB-S2 compliant is very clearly laid out by the operational parameters of the transmission system description. However, as long as a receiving device, that includes a decoder, complies with these operational parameters specified within the DVB-S2 standard, great latitude in the means of implementation is permissible. The generation of signals on the transmission end of a communication channel is clearly laid out within the DVB-S2 standard, and the means by which the receive processing of such signal (at the receiving end of a communication channel) may be performed is widely open to the designer. Clearly, a key design constrain of such receiving devices is to provide for the accommodation of such DVB-S2 signals while providing for very high performance while occupying a relatively small amount of area and having a relatively lower level of complexity.
Within the context of DVB-S2 as well as other types of communication systems, there continues to be a need in the art for faster and more efficient means by which LDPC coded signals (as well as other types of coded signals) may be decoded to provide for a variety of design constraints including operational speed, less computational complexity, less burdensome memory management, as well as overall lower BERs (Bit Error Rates) for various degrees of SNR (Signal to Noise Ratio).
Moreover, there is no means presently in the art to do layered decoding using a low density parity check matrix, H, that has a p×p sub-matrix, Hi,j, that is a sum of multiple permuted p×p identity matrices. For example, when a p×p sub-matrix, Hi,j, has more than one “1” value per row or per column, the prior art layered decoding approach does not work.
It is known in the art that the more constraints placed on the construction of an LDPC code inherently limits the LDPC code's performance. The fact that this prior art layered decoding approach can handle only p×p sub-matrices, Hi,j, having one “1” value per row or per column restricts the selection of LDPC codes that may be employed. By being restricted to only LDPC codes having this format, a designer does not have the flexibility to construct a better performing LDPC code while using this prior art layered decoding approach.